#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/12/10 08:45|08:45
# @Author  : yangdingyi
# @File    : 不同的二叉搜索树 II
# @Software: PyCharm
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n <= 0:
            return []
        data = [i for i in range(1, n + 1)]

        def work(data: List[int]) -> List[TreeNode]:
            if len(data) <= 0:
                return [None]
            ret = []
            for i, a in enumerate(data):
                l_list = work(data[:i])
                r_list = work(data[i+1:])
                for l_n in l_list:
                    for r_n in r_list:
                        rt = TreeNode(a)
                        rt.left = l_n
                        rt.right = r_n
                        ret.append(rt)
            return ret

        return work(data)


solve = Solution()
n = 3
print(n)
ans = solve.generateTrees(n)
print(ans)


def display(trees: List[TreeNode]) -> None:
    for i, tr in enumerate(trees):
        print('Tree[#{}]:'.format(i))

        def _display(nd: TreeNode, dep=1) -> None:
            if not nd:
                print('{}{}'.format(' ' * dep, nd.val if nd else None))
                return
            _display(nd.right, dep + 1)
            print('{}{}'.format(' ' * dep, nd.val if nd else None))
            _display(nd.left, dep + 1)

        _display(tr)


display(ans)
